/**
 * @file    GetCommonElements_V2.c
 * @brief   查找两个升序链表的公共元素，并生成新链表返回
 * @details
 *    - 输入：两个递增单链表（不带头结点）
 *    - 输出：一个新的链表（不带头结点），包含所有公共元素
 *    - 要求：不破坏原链表结构
 *    - 算法：双指针遍历比较，时间复杂度 O(n + m)
 *
 * @author  WangBlue
 * @date    2025-07-17
 * @version 2.0
 */

#include <stdio.h>
#include <stdlib.h>

// ------------------------- 结点结构定义 -------------------------

/**
 * @brief 单链表结点定义
 */
typedef struct node {
    int data;              ///< 数据域
    struct node *next;     ///< 指针域
} node, *link;

// ------------------------- 链表基本操作 -------------------------

/**
 * @brief 创建一个新的结点
 * @param value 数据值
 * @return 成功返回新结点指针，失败返回 NULL
 */
link createNode(int value) {
    link node = (link)malloc(sizeof(node));
    if (node == NULL) return NULL;
    node->data = value;
    node->next = NULL;
    return node;
}

/**
 * @brief 头插法插入结点
 * @param head 链表头指针地址
 * @param value 插入的数据
 */
void insertHead(link *head, int value) {
    link node = createNode(value);
    if (!node) return;
    node->next = *head;
    *head = node;
}

/**
 * @brief 尾插法插入结点
 * @param head 链表头指针地址
 * @param value 插入的数据
 */
void insertTail(link *head, int value) {
    link node = createNode(value);
    if (!node) return;

    // 空链表处理：新结点即为头结点
    if (*head == NULL) {
        *head = node;
        return;
    }

    // 否则遍历到末尾插入
    link cur = *head;
    while (cur->next != NULL) {
        cur = cur->next;
    }
    cur->next = node;
}

/**
 * @brief 打印链表所有元素
 * @param head 链表头指针地址
 */
void printLink(link *head) {
    if (*head == NULL) return;
    link cur = *head;
    while (cur != NULL) {
        printf("value is %d\n", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

/**
 * @brief 释放链表的所有结点内存
 * @param head 链表头指针地址
 */
void destroy(link *head) {
    if (*head == NULL) return;
    link cur = *head;
    while (cur != NULL) {
        link temp = cur->next;
        free(cur);
        cur = temp;
    }
    *head = NULL;
    printf("SUCCESS\n");
}

// ------------------------- 查找公共元素 -------------------------

/**
 * @brief 获取两个有序链表的公共元素，构成新链表
 * @param pa 链表1头指针地址
 * @param pb 链表2头指针地址
 * @return 返回新链表头指针（不带头结点）
 */
link getComEle(link *pa, link *pb) {
    if (*pa == NULL || *pb == NULL) return NULL;

    link l1 = *pa;
    link l2 = *pb;
    link head = NULL;     // 新链表头
    link tail = NULL;     // 新链表尾（用于尾插）

    // 双指针遍历两个链表
    while (l1 != NULL && l2 != NULL) {
        if (l1->data < l2->data) {
            l1 = l1->next;
        } else if (l1->data > l2->data) {
            l2 = l2->next;
        } else {
            // 相等，添加至结果链表
            link newNode = createNode(l1->data);
            if (!newNode) return NULL;

            if (tail == NULL) {
                head = tail = newNode; // 初始化结果链表
            } else {
                tail->next = newNode;
                tail = newNode;
            }

            l1 = l1->next;
            l2 = l2->next;
        }
    }

    return head;
}

// ------------------------- 主函数测试 -------------------------

int main() {
    // 创建第一个链表 head：1 → 2 → 3
    link head = NULL;
    insertTail(&head, 1);
    insertTail(&head, 2);
    insertTail(&head, 3);

    // 创建第二个链表 head2：2 → 3 → 4
    link head2 = NULL;
    insertTail(&head2, 2);
    insertTail(&head2, 3);
    insertTail(&head2, 4);

    // 获取公共元素链表：2 → 3
    link newNode = getComEle(&head, &head2);
    printLink(&newNode);

    // 内存清理（建议）
    destroy(&head);
    destroy(&head2);
    destroy(&newNode);

    return 0;
}
